package com.maishi.programmer.jainzhioffer;

/**
 * Created by brossdong on 2018/3/25.
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
 * 使得所有奇数位于数组的前半部分，所有的偶数位于数组的后半部分
 */
public class TestProblem21 {
    /**
     * 给出一种模式
     * 解决一系列的方法
     */

    /**
     * 判断是否是奇数
     */
    public boolean isEven (int n) {
        return (n & 0x1) == 1;
    }

    public void order (int arr[]) {
        if (arr == null) return;
       /*
       定义两个指针 一个指向第一个位置  另一个指向最后一个位置
       这样顺序被换了
        int i = 0;
        int j = arr.length - 1;
        */

        /*
        快排不稳定
        顺序换了
        while (i < j) {
            //i是偶数 j是奇数  进行交换
            if (!isEven(arr[i]) && isEven(arr[j])) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            else if (isEven(arr[i]) && isEven(arr[j])) {
                i++;
            }else if (!isEven(arr[i]) && !isEven(arr[j])) {
                j--;
            }else {
                i++;
                j--;
            }
        }*/

        /**
         * 定义两指针,第一个从头开始begi
         * 第二个从begin+1开始
         */
        int begin = 0,from;
        while (begin < arr.length) {
            //如果不是偶数,继续前行
            while (begin < arr.length && (arr[begin] & 0x1) == 1) {
                begin++;
            }
            //如果下一个不是奇数,继续前行
            from = begin + 1;
            while (from < arr.length && (arr[from] & 0x1) != 1) {
                from++;
            }
            if (from < arr.length) {
                int temp = arr[from];
                for (int i = from -1;i >= begin;i--) {
                    arr[i+1] = arr[i];
                }
                arr[begin++] = temp;
            }else {
                break;
            }
        }


    }

    public static void main(String[] args){
        TestProblem21 test = new TestProblem21();
        int[] arr= {1,2,3,4,5,6,7};
        test.order(arr);
        for(int i = 0;i<arr.length ;i++){
            System.out.print(arr[i]+",");
        }
    }
}
